package _1_单调栈

/*
*
https://leetcode.cn/problems/trapping-rain-water/

42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，
在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

*
*
*	    *
*	    *
* * *   *
* * * * *
6 2 2 1 3   高度

思路:
暴力解法:

	for循环遍历数组, 模拟以每个柱子为底的情况,
	里面还需一个循环, 求右边比当前柱子高的柱子的高度, 以及左边比当前高度高的柱子的高度
	这样就能求出当前柱子形成的凹槽

	由于遍历每个柱子, 都需要分别向左、向后再遍历一次, 复杂度为n方

单调栈解法:

	----------------------------
								|
	----------------------------

	如果当前元素 > 栈口的元素, 那么栈口元素找到了右边第一个比自己大的元素
	但是还需要找到左边第一个比自己高的柱子, 这样才能形成凹槽面积
	其实, 第二个比当前元素小的栈口元素, 就是左边第一个比当前柱子大的元素

单调栈就是保持栈内元素有序. 需要我们自己维持顺序, 但是没有现成容器时使用

考点1: 那么本题使用单调栈的顺序, 是递增还是递减呢?
  - 从栈口(元素从栈口弹出)到栈底的顺序应该是递增.
    因为一旦发现添加的柱子高度大于栈口元素了, 此时就出现凹槽了,
    栈口元素就是凹槽底部的柱子, 栈口第二个元素就是凹槽左边的柱子, 而添加的元素就是凹槽右边的柱子

考点2: 如果遇到相同高度的柱子怎么办?
  - 遇到相同的元素, 更新栈内下标, 就是将栈内元素(旧下标)弹出, 将新元素(新下标)加入栈中
    例如 5 5 1 3这种情况. 如果添加第二个5的时候就应该将第一个5的下标弹出, 把第二个5添加到栈中
    因为需要获取宽度的时候, 如果遇到相同高度的柱子, 需要使用右边的柱子来计算宽度

考点3: 栈中要保存什么数值?
  - 使用单调栈, 也是通过 长*宽 来计算雨水面积的
    长就是通过柱子的高度来计算, 宽是通过柱子之间的下标来计算

具体处理过程:

  - 逻辑主要分为三种情况:
    情况1: 当前遍历的元素(柱子) < 栈顶元素的高度	height[i] < height[st.top()]
    情况2: 当前遍历的元素(柱子) = 栈顶元素的高度	height[i] == height[st.top()]
    情况3: 当前遍历的元素(柱子) > 栈顶元素的高度	height[i] > height[st.top()]

    先将下标0的柱子加入到栈中, st.push(0) 栈中存放遍历过的元素的下标, 所以将下标0加进来
    然后从下标1开始遍历所有的柱子, for (int i=1; i<height.size(); i++)
    如果当前遍历的元素(柱子) < 栈顶元素的高度, 就把这个元素加入栈中, 因为没有打破栈的单调性
    代码如下:
    if (height[i] < height[st.top()]) {
    st.push(i)
    }

    如果当前遍历的元素(柱子) == 栈顶元素的高度, 要更新栈顶元素, 因为遇到相同高度的柱子, 需要使用最右边的柱子来计算宽度
    if (height[i] == height[st.top()]) {
    st.pop()
    st.push(i)
    }
    如果当前遍历的元素(柱子)高度大于栈顶元素的高度, 此时就出现凹槽了
    将栈顶元素弹出, 这个就是凹槽的底部, 也就是中间位置, 下标记位mid, 对应的高度为 height[mid]
    此时的栈顶元素st.top(), 就是凹槽的左边位置, 下标为st.top(), 对应的高度为height[st.top()]
    当前遍历的元素i, 就是凹槽右边的位置, 下标为i, 对应的高度为 height[i]

    此时发现, 其实就是栈顶和栈顶的下一个元素做左右柱子, 当前遍历的元素作为底柱子, 来接雨水

    那么雨水高度: min(左柱子, 右柱子) - 底柱子高度  int h = min(height[st.top()], height[i]) - height[mid]
    雨水宽度: 右柱子下标 - 左柱子下标 - 1 (因为只求中间宽度) int w = i - st.top() - 1

    当前凹槽雨水的体积就是: h * w
*/
func trap(height []int) int {

	if len(height) <= 2 { //数组长度如果小于等于2, 那么不能接住雨水, 直接返回即可
		return 0
	}

	//声明切片, 初始容量为1, 容量为height数组长度
	st := make([]int, len(height)) // 切片模拟单调栈，st存储的是高度数组下标
	st = append(st, 0)             //将0柱子放入栈

	var res int //声明结果变量

	for i := 1; i <= len(height)-1; i++ { //0下标柱子已经放入栈了, 从1遍历即可
		if height[i] < height[st[len(st)-1]] { //如果当前元素 < 栈口元素, 没有打破栈的单调递增性, 直接加入栈
			st = append(st, i)
		} else if height[i] == height[st[len(st)-1]] { //如果与栈口元素相等, 将栈口元素弹出, 将当前元素下标加入栈中
			st = st[:len(st)-1] // 比较的新元素和栈顶的元素相等，去掉栈中的，入栈新元素下标
			st = append(st, i)
		} else { //否则当前元素 > 栈口元素了, 满足了形成雨水的凹槽, 累加计算雨水体积
			for len(st) != 0 && height[i] > height[st[len(st)-1]] { //只要栈不为空 && 当前元素>栈口元素
				mid := st[len(st)-1] //获取栈顶元素(中柱子)
				st = st[:len(st)-1]  //弹出栈顶元素
				if len(st) != 0 {
					//计算当前三个柱子形成的雨水面积, 与结果计数累加 右柱子	左柱
					temp := (min(height[i], height[st[len(st)-1]]) - height[mid]) *
						(i - st[len(st)-1] - 1)
					res += temp //雨水体积累加
				}
			}

			st = append(st, i) //计算完毕后, 将当前柱子下标, 加入栈中
		}
	}
	return res
}

func min(x, y int) int {
	if x >= y {
		return y
	}
	return x
}
